Weee... check this out:

A full scan of a table containing ten million items requires up to ten 
million operations. (On average, half that.) Using binary chop, it takes 
only the binary logarithm of that - about 25 operations.

If a computer can process 1,000 operations per second (bearing in mind, 
comparing a record to the target being looked up is a far few machine 
instructions), we achieve the following times:

   Full scan:   2.777 hours
   Binary chop: 0.025 seconds

So one way takes almost three hours to do a single lookup, while the 
other can do 40 lookups per second. O(log N) FTW!

But wait, check this out. Perhaps you are somehow unimpressed with 
taking a 3-hour operation and completing it in 1/40th of a second. Well 
try this for size:

Assume there are 10^80 atoms in the observable universe. If you 
sequentially full scan then all, one by one, at 1,000 atoms per second, 
it'll take you 10^77 seconds.

This is longer than the universe has existed (10^11 seconds). 
Hypothetically, it's longer than it will take for all the energy in the 
universe to be exhausted. By the time 10^77 seconds is up, the universe 
will have died a cold, dark, silent death of total equilibrium a very 
long time ago.

In short, this procedure is so slow that there isn't enough time or 
energy in the whole of the known universe to actually complete it. (But 
then, who's going to pin a unique record to every atom in the universe 
anyway?)

On the other hand, according to my sums 10^80 is roughly 2^266. Thus, 
the binary chop algorithm requires only 266 operations, and can easily 
complete the entire process in well under a second. [If we assume 
completely random access to any atom in the universe, which completely 
defies several known physical laws...]

Like, wow man!

-- 
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*

Post a reply to this message